package clsFour3;

import java.util.ArrayList;
import java.util.List;
import edu.princeton.cs.algs4.Bag;

public class EdgeWeightedGraph {
    private final int V;             // 顶点总数
    private int E;                   // 边的总数
    private Bag<Edge>[] adj;         // 邻接表

    // 构造函数，创建一个含有 V 个顶点的图
    public EdgeWeightedGraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<Edge>();
        }
    }

    // 通过输入流创建图（见练习 4.3.9，具体实现需补充）
    public EdgeWeightedGraph(In in) {
        // 实现省略
    }

    // 返回图的顶点总数
    public int V() {
        return V;
    }

    // 返回图的边总数
    public int E() {
        return E;
    }

    // 添加一条边到图中
    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }

    // 返回与顶点 v 相邻的所有边
    public Iterable<Edge> adj(int v) {
        return adj[v];
    }

    // 返回图中的所有边
    public Iterable<Edge> edges() {
        List<Edge> list = new ArrayList<>();
        for (int v = 0; v < V; v++) {
            for (Edge e : adj[v]) {
                if (e.other(v) > v) {
                    list.add(e); // 确保每条边只被添加一次
                }
            }
        }
        return list;
    }
}